// https://leetcode.cn/problems/kth-missing-positive-number/

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int n = arr.size();
        int l = -1, r = n;
        while (l + 1 < r) {
            int mid = l + r >> 1;
            if (arr[mid] - mid - 1 < k) l = mid;
            else r = mid;
        }
        if (r == n - 1 && arr[r] - r - 1 < k) return k + n;
        return r + k;
    }
};